昨天我們簡單介紹了 Learned Index，主要是學習資料在array中的分布，建置Model，使用Model預測出資料在array中的位置。

那是學習甚麼...呢 ? 甚麼分布 ?

Ans: 學習CDF的分布

CDF全名為 Cumulative Density Function 累積分布函數，一種機率函數，計算小於等於x的機率。

參考資料

https://zh.wikipedia.org/wiki/%E7%B4%AF%E7%A7%AF%E5%88%86%E5%B8%83%E5%87%BD%E6%95%B0

https://www.youtube.com/watch?v=RlNfklkZPlo

Kraska et al. 他們發現了一件有趣的事情，在array中已排序好的key值，key值經由CDF分布函數產生的結果再乘以所有key值數量，會近似於key值自己所在的位置 ! (有點難懂厚 XD)

也就是說，使用CDF函數可以知道key值的位置。

Position = CDF(key) * N

一張圖勝過千言萬語 ~

如上圖所示，N代表所有Key值數量在這裡為9，排序好的Key有 1, 5, 12, 14, 20, 35, 40, 89, 90，Key值的位置(Pos)，也就是他們在array中的位置，分別為0, 1, 2 ... 8

只要使用CDF函式就可以 近似 找出Key值的位置 !

不是近五、近六，是近似喔XD